/**
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 *
 *https://leetcode.cn/problems/recover-binary-search-tree/
 * 思路：（暴力）
 我们需要考虑两个节点被错误地交换后对原二叉搜索树造成了什么影响。对于二叉搜索树，我们知道如果对其进行中序遍历，得到的值序列是递增有序的，而如果我们错误地交换了两个节点，等价于在这个值序列中交换了两个值，破坏了值序列的递增性。
 我们来看下如果在一个递增的序列中交换两个值会造成什么影响。假设有一个递增序列 a=[1,2,3,4,5,6,7]a=[1,2,3,4,5,6,7]。如果我们交换两个不相邻的数字，例如 2 和 6，原序列变成了 a=[1,6,3,4,5,2,7]a=[1,6,3,4,5,2,7]，那么显然序列中有两个位置不满足 a_i<a_{i+1}
 ，在这个序列中体现为 6>3，5>2，因此只要我们找到这两个位置，即可找到被错误交换的两个节点。如果我们交换两个相邻的数字，例如 2 和 3，此时交换后的序列只有一个位置不满足 a_i<a_{i+1
 。因此整个值序列中不满足条件的位置或者有两个，或者有一个。
 至此，解题方法已经呼之欲出了：


 */
class RecoverTreeBaoLi {
    public void recoverTree(TreeNode root) {
        List<Integer> nums=new ArrayList<>();
        inorder(root,nums);
        int[] swapNum=findNums(nums);
        swap(root,2,swapNum[0],swapNum[1]);
        return;
    }
    public void swap(TreeNode root,int count,int x,int y){
        if(root==null){
            return;
        }

        if(root!=null){
            if(root.val==x||root.val==y){
                root.val=root.val==x?y:x;
                if(--count==0){
                     return;
                }
            }
        }
        swap(root.left,2,x,y);
        swap(root.right,2,x,y);
    }
    public void inorder(TreeNode root,List<Integer> nums){
        if(root==null){
            return;
        }
        inorder(root.left,nums);
        nums.add(root.val);
        inorder(root.right,nums);
    }
    public int[] findNums(List<Integer> nums){
        int index1=-1;
        int index2=-1;
        int len=nums.size();
        for(int i=0;i<len-1;i++){
            if(nums.get(i)>nums.get(i+1)){
                index2=i+1;
                if(index1==-1){
                    index1=i;
                }else{
                    break;
                }
            }
        }
        int x=nums.get(index1),y=nums.get(index2);
        return new int[]{x,y};
    }
}